#include <iostream>
using std::cout;
using std::endl;
using std::cin;

#include <string>
using std::string;

#include <vector>
using std::vector;

// class huffman_tree;
// void swap(huffman_tree& t1, huffman_tree&t2);

#include "heap.h"

#include <utility>
using std::swap;

#include <queue>
#include <functional> // for std::greater

void test();

struct huffman_node
{
    char m_ch;
    int m_weight;
    huffman_node* m_left;
    huffman_node* m_right;

    huffman_node(int weight = 0, int ch = 0, huffman_node* left = nullptr, huffman_node* right = nullptr)
        : m_ch(ch)
        , m_weight(weight)
        , m_left(left)
        , m_right(right)
    {

    }

 

};


// 这个类就是一个二叉树, 加权外部路径长度, nono... 这个就是哈夫曼树
class huffman_tree
{
public:
    huffman_tree(int weight = 0, int ch = 0, huffman_tree* left = nullptr, huffman_tree* right = nullptr)
    {
        m_root = new huffman_node(weight, ch);
        if (left == nullptr)
        {
            m_root->m_left = nullptr;
        }
        else 
        {
            m_root->m_left = left->m_root;
        }

         if (right == nullptr)
        {
            m_root->m_right = nullptr;
        }
        else 
        {
            m_root->m_right = right->m_root;
        }
    }

    huffman_tree(const huffman_tree& x)
    {
        // recursion_delete(m_root);
        // 别忘了, 这也是构造函数, 它本身就是在进行初始化
        m_root = recursion_copy(x.m_root);
    }

    huffman_tree& operator=(const huffman_tree& x)
    {
        huffman_tree tmp = x;
        swap(tmp.m_root, m_root);
        return *this;
    }

    ~huffman_tree()
    {
        recursion_delete(m_root);
        m_root = nullptr;
    }

    int& get_root_weight()
    {
        return m_root->m_weight;
    }

    char& get_root_char()
    {
        return m_root->m_ch;
    }

    huffman_node*& get_root()
    {
        return m_root;
    }

    void set_root(huffman_node* x)
    {
        m_root = x;
    }

    // 两颗树之间的比较 
    bool operator<(const huffman_tree& x) const 
    {
        return m_root->m_weight < x.m_root->m_weight;
    }

    bool operator==(const huffman_tree& x) const 
    {
        return m_root->m_weight == x.m_root->m_weight;
    }

    bool operator>(const huffman_tree& x) const 
    {
        return !(*this < x || *this == x);
    }

    bool operator>=(const huffman_tree& x) const
    {
        return !(*this < x);
    }

    // 编码长度
    int code_length() const
    {
        if (recursion_hight(m_root) == 1)
        {
            return m_root->m_weight;
        }

        return recursion_code_length(m_root, 1);
    }

private:
    huffman_node* m_root;

    void recursion_delete(huffman_node* root)
    {
        if (root == nullptr)
        {
            return;
        }

        recursion_delete(root->m_left);
        recursion_delete(root->m_right);
        delete root;
    }

    huffman_node* recursion_copy(huffman_node* root)
    {
        if (root == nullptr)
        {
            return nullptr;
        }

        huffman_node* tmp = new huffman_node(root->m_weight, root->m_ch);
        tmp->m_left = recursion_copy(root->m_left);
        tmp->m_right = recursion_copy(root->m_right);

        return tmp;
    }

    int recursion_code_length(huffman_node* root, int height) const 
    {
        if (root == nullptr)
        {
            return 0;
        }

        if (root->m_left == nullptr && root->m_right == nullptr)
        {
            return (height-1) * root->m_weight;
        }

        int left_len = recursion_code_length(root->m_left, height + 1);
        int right_len = recursion_code_length(root->m_right, height+1);

        return left_len + right_len;
    }

    int recursion_hight(huffman_node* root) const 
    {
        if (root == nullptr)
        {
            return 0;
        }

        int left_hight = recursion_hight(root->m_left);
        int right_hight = recursion_hight(root->m_right);
        int hight = left_hight > right_hight ? left_hight + 1 : right_hight + 1;

        return hight; 
    }

};

// void swap(huffman_tree& t1, huffman_tree&t2)
// {
//     huffman_node* tmp = t1.get_root();
//     t1.set_root(t2.get_root()); // t1.get_root() = t2.get_root();
//     t2.set_root(tmp);
// }

// 建huffman树
void solution()
{
    // 输入
    string s;
    std::getline(cin, s);

    if (s.size() == 0)
    {
        cout << 0 << endl;
        return;
    }

    // 统计该字符串中每种字符的频率
    vector<int> v(26); // 索引0-25
    for (int i = 0; i < s.size(); ++i)
    {
        ++(v[s[i] - 'a']);
    }

    // 建哈夫曼树, 每一个节点都是一颗huffman tree, 但它不是这个字符串的huffman tree
    // 每一种情况频率的字符串的huffman tree都是一种情况
    vector<huffman_tree> v2;
    //heap<huffman_tree> h;
    for (int i = 0; i < 26; ++i)
    {
        if (v[i] != 0)
        {
            v2.push_back(huffman_tree(v[i], 'a'+i));
            //h.push(huffman_tree(v[i], 'a'+i));
        }
    }

    heap<huffman_tree> h(v2);

    while (h.size() != 1)
    {
        huffman_tree* a = new huffman_tree(h.top()); 
        h.pop();
        huffman_tree* b = new huffman_tree(h.top());
        h.pop();

        h.push(huffman_tree(a->get_root_weight() + b->get_root_weight(), 0, a, b)); // 他会把a和b给delete掉
    }
    
    cout << h.top().code_length() << endl;
    
}

int main()
{
    //solution();
    test();

    return 0;
}

void test()
{
    huffman_tree t1(1, 'a');
    huffman_tree t2(2, 'b');
    t2.~huffman_tree();

    huffman_tree t3 = t2;

    swap(t1, t2);

    // heap<huffman_tree> h;
    // h.push(1);
    // h.push(2);
    // h.push(3);
    // h.push(4);
    // h.push(5);
    // h.push(6);
    // h.push(7);

    // h.pop();
    // h.pop();
    // h.pop();
    // h.pop();
    // h.pop();
    // h.pop();
    // h.pop();

}